Maintaining a Tree with an Adjacency List

Many operations can be accomplished using the Adjacency List.

Inserting a new leaf node#

Some operations are simple to accomplish with an Adjacency List, such as adding a new leaf node.

Let’s see how we can add a new leaf node:

After inserting the record, let’s retrieve the data in the next playground.

Relocating a single node or a subtree#

The process of relocating a single node or a subtree is also easy. Have a look at the next query for more clarification:

We are updating the table by setting 3 as a parent of 6 in the query. Now the parent of node 6 is 3. Let’s retrieve the Comments table to see how this query has affected the table.

Deleting a node in Adjacency List#

The process of deleting a node from a tree is more complex. If we want to delete an entire subtree, we have to first issue multiple queries to find all descendants. Only then can we remove the descendants from the lowest level up to satisfy the foreign key integrity.

Let’s find out all the descendants of each node in a tree. Here is the query that displays the descendants of node 4.

Let’s repeat the same query to find out the descendants of node 5.

The given query must not return any records because node 5 has no child.

The following query displays the descendants of node 6.

Finally, let’s check the descendants of node 7.

There are no descendants of 7, so the given query must not return any records.

Now, we will be deleting the descendant nodes that we just found out in the previous queries.

Let’s retrieve the remaining data after deleting these comments.

We can use a foreign key with the ON DELETE CASCADE modifier to automate this, as long as we are sure that we always want to delete the descendants instead of promoting or relocating them.

In case we want to delete a non-leaf node instead, and promote its children or move them to another place in the tree, we first need to change the parent_id of children and then delete the desired node.

Let’s try to delete node 6. The steps for removing this node would include:

• Retrieving the subtree of the node to be deleted
• Updating the parent of the node’s children (if any)
• Delete the node

First, we will retrieve the subtree of a node.

After we have retrieved the subtree and we know that node 6 has one child node (node 7), we will update the parent_id of node 7, so that this node keeps connected to the tree after the deletion of its parent.

Let’s try to run this code in the following playground to see the effects of this query on the database.

Now we can delete the node because its children will stay connected to the tree even after its deletion.

Let’s try to run the query in the following playground.

These are examples of operations that require multiple steps when we use the Adjacency List design. That’s a lot of code we have to write for tasks that a database should make simpler and more efficient.